1. Field of the Invention
The present invention relates generally to color conversion and more particularly to color conversion using interpolation of values using look up tables.
2. Description of the Related Art
Electronic imaging systems necessarily involve color space conversions. A system that captures images in Red Green Blue (RGB) space and reproduces them on a Cyan Magenta Yellow blacK (CMYK) printer needs to convert each pixel of the image from RGB space to CMYK space. Also inherent in all but the simplest color space conversion is nonlinearity of the transformation. For example, the RGB to CMYK conversion is usually not a linear transformation. One common technique to handle general nonlinear transformation is through the use of a Look-Up Table (LUT). To generate a LUT, a rectangular grid of nodes is imposed on the source color space and a value in the destination color space is evaluated at each of the nodes. In use, for any color in the source color space that is not one of the nodes, an interpolation algorithm is used.
FIG. 1 is a block diagram illustrating use of a LUT by a color device to map from one color space to another. In this example, a data processing system, such as computer 100, maps color values of a first color device, such as color scanner 99, to color values for a second color device, such as color printer 101. For example, the data processing system may map RGB color value 102 generated by the color scanner to CMYK color value 104 used by the color printer. The data processing system does so using one of several LUTs, 106, 108, 110 and 112. The choice of the interpolation algorithm depends on the geometrical arrangement of the sampling points. If the points are totally unstructured, or what is known as a “point cloud” 106, then interpolation methods suitable for scattered data are used. Such methods are generally slow, and are employed only in situations where the sampling locations cannot be arranged.
On the other extreme of point clouds is the case where the sampling points fall on a rectangular grid 108. The simplest situation of a rectangular grid is one with uniform sampling in each channel. Given an input point, its enclosing cell can be efficiently located, then an interpolation algorithm, such as tetrahedral interpolation, can be used to perform the interpolation within this enclosing cell.
A slightly more complicated situation is a rectangular grid 110 with non-uniform sampling in each channel. In the case of non-uniformly sampled rectangular grid, the enclosing cell can still be determined quite easily, though not as efficiently as the uniform case. Once the enclosing cell is determined, interpolation within the cell is done the same way as the uniform case.
In between the totally unstructured configuration of point cloud, and the totally structured configuration of a rectangular grid lies an “adaptive rectangular grid” 112. An adaptive rectangular grid still employs rectangular grids (possibly non-uniformly sampled) on subspaces, but these grids are not compatible as a whole. Adaptive sampling is useful to reduce the sampling rate, that is, increase the storage efficiency, in a region of the color space that is less important. For example, in the standard IT8.7/3 target for CMYK printers, sampling on each CMY “plane” for a fixed K is uniform rectangular, but the sampling rate is successively reduced as K increases, because the colors get darker and variations become smaller to make high sampling rate wasteful.
A traditional approach to performing interpolation on an adaptive rectangular grid is called Sequential Linear Interpolation (SLI). The key step reduces an n-dimensional interpolation to two (n−1)-dimensional interpolations and a 1-dimensional interpolation, and the same procedure can be applied to each of the (n−1)-dimensional interpolation problems, hence the name “sequential”.
Several things are not desirable about SLI:    1. SLI does not preserve all the symmetries. In fact, suppose the grid is uniformly rectangular, and SLI is applied all the way to dimension 1. This results in the same result as multilinear interpolation (usually called cubic interpolation in the case of 3 dimensions). Points on the principal diagonal are interpolated using all the corner points of the cube. This is not desirable if the principal diagonal is the gray axis (as in RGB space) because one prefers grays to be interpolated using sampling points on the gray axis only.    2. The SLI step is also not necessarily compatible with the interpolation used on sandwiching planes. For instance, if tetrahedral interpolation is used on each sandwiching plane, then SLI produces a “hybrid” that is “bilinear”, linear on each sandwiching plane, and linear in the transverse direction between them. True tetrahedral interpolation in the full dimension would be linear in each subdividing tetrahedron.    3. SLI handles the basic geometrical configuration with 2 sandwiching linear hyperplanes where the hyperplanes are provided by n−1 coordinates and the transverse direction to the hyperplanes provided by the remaining coordinate. There are other more complicated geometrical situations which SLI cannot handle, or can do so only awkwardly. One scenario is the “gap interpolation problem” between incompatible grids in different dimensions. FIG. 2 depicts a simple 2-dimensional situation in a x1x2 space where the interior of the space is covered a rectangular grid, and each of the x1 and x2 axis is covered by different 1-D grids, and furthermore these grids are not compatible. To interpolate in the gap space, consider the three input points P1, P2 and P3. While P1 and P2 can probably be handled by SLI as indicated in the figure, there is no natural way to handle P3. One possibility is to try and apply SLI in the x1 direction, interpolating between A3 and B3, where B3 itself needs to be interpolated first. Another possibility is to apply SLI in the other direction, ending in an interpolation between C3 and D3. Worst of all, one may get different results from each approach. Clearly, when the sandwiching geometric objects are more complicated than linear hyperplanes, SLI is not an ideal tool.
Therefore, a need exists for a color conversion system that employs computational efficient interpolation and yet manages geometrically complex LUTs. Various aspects of the present invention meet such a need.